893E - Counting Arrays - CodeForces Solution

#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
const int mod = 1000000007;
using namespace std;

int qkpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = (ll)res * x % mod;
		x = (ll)x * x % mod;
		y >>= 1;
	}
	return res;
}
struct mint{
	int x;
	mint() { x = 0; }
	mint(int _x) { x = _x % mod; }
	mint operator + (mint y) { return (x + y.x) % mod; }
	mint operator - (mint y) { return (x - y.x + mod) % mod; }
	mint operator * (mint y) { return (ll)x * y.x % mod; }
	mint operator / (mint y) { return (ll)x * qkpow(y.x, mod - 2) % mod; }
}; 

mint f[1000005], ans, sum;
mint C(int a, int b) {
	return f[a] / (f[b] * f[a - b]);
}

int q, n, m;

int main() {
	f[0] = 1;
	for (int i = 1; i <= (int)1e6; i++) {
		f[i] = f[i - 1] * i;
	}

	scanf("%d", &q);
	while (q--) {
		scanf("%d%d", &n, &m);
		int sq = (int)sqrt(n); 
		ans = 1;
		
		for (int i = 2, cnt; i <= sq; i++) {
			cnt = 0;
			while (n % i == 0) {
				n /= i;
				cnt ++;
			}
			if (!cnt) continue;
			
			sum = 0;
			for (int h = 1; h <= min(m, cnt); h++) {
				sum = sum + C(m, h) * C(cnt - 1, h - 1);
			}
			ans = ans * sum;
		}
		if (n > 1) ans = ans * m;
		
		ans = ans * qkpow(2, m - 1);
		printf("%d\n", ans.x);
	}
	return 0;
}